package com.fyl.basic_algorithm.backtrack;

/**
 * @Description:
 * @author:fyl
 * @date 2021/4/7 15:39
 * @Modified By:
 * @Modified Date:
 */
public class Pack_01 {
    public static int maxW = Integer.MIN_VALUE;
    private static int n = 5; //物品个数
    private static int w = 10; //背包承受最大重量
    private static boolean[][] mem = new boolean[n][w];  //备忘录，默认值为false

    /**
     * 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，
     * 那可以这样调用函数： f(0, 0, a, 10, 100)
     *
     * @param i     表示考察到哪个物品了
     * @param cw    表示当前已经装进去的物品的重量和
     * @param items 表示每个物品的重量
     * @param n     表示物品的个数
     * @param w     表示背包的重量
     */
    public static void f(int i, int cw, int[] items, int n, int w) {
        if (cw == w || i == n) { //cw == w表示装满了；i==n表示考察完所有物品
            if (cw > maxW) maxW = cw;
            return;
        }
        if (mem[i][cw]) return;
        mem[i][w] = true; //记录(i,w)这个状态
        f(i + 1, cw, items, n, w);
        if (cw + items[i] <= w) {  //已经超过背包承受的重量的时候就不在装了。此时还未超过
            f(i+1,cw+items[i],items,n,w);
        }
    }

    public static void main(String[] args) {
        int[] a={2,2,4,6,3};
        f(0,0,a,5,9);
    }
}
